// 数组划分、数组分块
// 两个指针将数组划分两块：已经处理过的区间，未处理的区间
// 注意：双指针/数组分块题目 不一定每次都是从左向右遍历，有时也需要从右向左遍历

// 例题 2：
//给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
//        注意：请不要在超过该数组长度的位置写入元素。
//        请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
//
//        示例 1：
//
//        输入：arr = [1,0,2,3,0,4,5,0]
//        输出：[1,0,0,2,3,0,0,4]
//        解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]
//        示例 2：
//
//        输入：arr = [1,2,3]
//        输出：[1,2,3]
//        解释：调用函数后，输入的数组将被修改为：[1,2,3]
//
//
//        提示：
//
//        1 <= arr.length <= 104
//        0 <= arr[i] <= 9

// 解题思路：
//  left 负责扫描数组，识别 0 元素和非 0 元素，确定需要复写的最后一个元素的位置
//  right 负责移动并找数组的最后一个位置或者数组最后一个元素的下一个位置
//  [0, left]: 需要复写的元素区间，  [right, n - 1]:已经复写的区间
class DuplicateZeros {
    public void duplicateZeros(int[] arr) {
        int n = arr.length;
        int left = 0;//扫描数组
        int right = -1;//找最后一个元素的位置
        // 1. 找最后一个需要复写的元素
        while(left < n){
            if(arr[left] != 0) right++;
            else right += 2;
            if(right >= n - 1) break;
            left++;
        }
        // 2. 处理边界情况
        if(right == n) {
            arr[n - 1] = 0;
            right -= 2;
            left--;
        }
        //3. 完成复写工作
        while(left >= 0){
            if(arr[left] != 0){
                arr[right] = arr[left];
                right--;
            }else {
                arr[right] = 0;
                arr[right - 1] = 0;
                right -= 2;
            }
            left--;
        }
    }
}
